package main

import (
	"fmt"
	"go-study/algorithm/standard"
	stdSort "sort"
)

// 如何对有大量重复的数字的数组排序

func main() {
	arr := []int{15, 12, 15, 2, 2, 12, 2, 3, 12, 100, 3, 3}
	s := &sort{}
	s.sort(arr)
	for _, v := range arr {
		fmt.Print(v, " ")
	}
	fmt.Println()

	arr = []int{15, 12, 15, 2, 2, 12, 2, 3, 12, 100, 3, 3}
	sortHash(arr)
	for _, v := range arr {
		fmt.Print(v, " ")
	}
	fmt.Println()
}

// 哈希法
func sortHash(arr []int) {
	dataCount := map[int]int{}
	series := make([]int, 0)
	for _, v := range arr {
		if val, ok := dataCount[v]; ok {
			dataCount[v] = val + 1
		} else {
			dataCount[v] = 1
			series = append(series, v)
		}
	}
	index := 0
	stdSort.Ints(series)
	for _, v := range series {
		val := dataCount[v]
		for i := val; i > 0; i-- {
			arr[index] = v
			index++
		}
	}
}

// AVL 数
type sort struct{}

// 中序遍历 AVL 树，把遍历的结果放入到数组中
func (p *sort) inorder(arr []int, root *standard.AVLNode, index int) int {
	if root != nil {
		index = p.inorder(arr, root.Left, index)
		for i := 0; i < root.Count; i++ {
			arr[index] = root.Data
			index++
		}
		index = p.inorder(arr, root.Right, index)
	}
	return index
}

// 得到数的高度
func (p *sort) getHeight(node *standard.AVLNode) int {
	if node == nil {
		return 0
	} else {
		return node.Height
	}
}

// 把以 y 为根的子树向右旋转
func (p *sort) rightRotate(y *standard.AVLNode) *standard.AVLNode {
	x := y.Left
	t2 := x.Right
	x.Right = y
	y.Left = t2
	y.Height = max(p.getHeight(y.Left), p.getHeight(y.Right))
	x.Height = max(p.getHeight(x.Left), p.getHeight(x.Right))
	return x
}

// 把以 x 为根的子树向左旋转
func (p *sort) leftRotate(x *standard.AVLNode) *standard.AVLNode {
	y := x.Right
	t2 := y.Left
	y.Left = x
	x.Right = t2
	x.Height = max(p.getHeight(x.Left), p.getHeight(x.Right))
	y.Height = max(p.getHeight(y.Left), p.getHeight(y.Right))
	return y
}

func (p *sort) insert(root *standard.AVLNode, data int) *standard.AVLNode {
	if root == nil {
		return standard.NewAVLNode(data)
	}

	if data == root.Data {
		root.Count++
		return root
	}

	if data < root.Data {
		root.Left = p.insert(root.Left, data)
	} else {
		root.Right = p.insert(root.Right, data)
	}

	root.Height = max(p.getHeight(root.Left), p.getHeight(root.Right))
	balance := p.getHeight(root)
	if balance > 1 && data < root.Left.Data {
		return p.rightRotate(root)
	} else if balance < -1 && data > root.Right.Data {
		return p.leftRotate(root)
	} else if balance > 1 && data > root.Left.Data {
		root.Left = p.leftRotate(root.Left)
		return p.rightRotate(root)
	} else if balance < -1 && data < root.Right.Data {
		root.Right = p.rightRotate(root.Right)
		return p.leftRotate(root)
	}

	return root
}

func (p *sort) sort(arr []int) {
	var root *standard.AVLNode
	for _, v := range arr {
		root = p.insert(root, v)
	}

	p.inorder(arr, root, 0)
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}
